import java.util.*;
import javax.sound.midi.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class PitchSorter extends JPanel
{
	private static final long serialVersionUID = 1L;
	private static boolean SWING = true;

	private Pitch[] array;
	
	private Scale scale;
	private int octaves;
	
	// GUI stuff
	public static final int AV_DELAY = 250;
	public static final int BAR_WIDTH = 10;
	public static final int WIN_HEIGHT = 350;
	private int i;
	private boolean on;
	private HashSet<Integer> sorted;
	
	// thread for pausing during demo
	private Pause pause;
	private boolean resume = false;
	
	public PitchSorter(Scale scale, int octaves)
	{
		if (octaves < 1 || octaves > 8)
			throw new IllegalArgumentException("Invalid range");
		
		array = new Pitch[scale.getLength()*octaves+1];
		
		this.scale = scale;
		this.octaves = octaves;
		
		reset();
		
		// GUI stuff
		sorted = new HashSet<Integer>(array.length);
		
		int width = BAR_WIDTH*(2*array.length+1);
		
		// height is 4px per note (88 total possible)
		setPreferredSize(new Dimension(width,WIN_HEIGHT));
		setOpaque(true);
		setBackground(Color.BLACK);
		
		KeyListener c = new Continuer();
		addKeyListener(c);
		setFocusable(true);
	}
	
	public void paintComponent(Graphics g)
	{
		super.paintComponent(g);

		for (int i=0; i < array.length; i++)
		{
			if (on && this.i == i)
				g.setColor(Color.RED);
			else
			{
				if (sorted.contains(i))
					g.setColor(Color.YELLOW);
				else
					g.setColor(Color.BLUE);
			}
			
			int x = BAR_WIDTH*(2*i+1);
			int h = 4 * array[i].freq.ordinal();
			g.fillRect(x, WIN_HEIGHT - h, BAR_WIDTH, h);
		}
	}
	
	public void reset()
	{
		int i = 0;
		Scale current = scale;
		for (int j=0; j < octaves; j++)
		{
			for (Pitch e : current.getScale())
				array[i++] = e;
			current = current.octaveUp();
			i--;
		}
		
		java.util.List<Pitch> list = Arrays.asList(array);
		Collections.shuffle(list);
		array = list.toArray(new Pitch[0]);
	}
	
	public void sort()
	{
		Arrays.sort(array);
	}
	
	public void sleep(int ms)
	{
		try {Thread.sleep(ms);}
		catch (InterruptedException ie) {ie.printStackTrace();}
	}
	
	public void pause()
	{
		if (!resume)
		{
			pause = new Pause();
			pause.run();
		}
	}
	
	/*
	public void play(int ms) throws MidiUnavailableException
	{
		Synthesizer synth = MidiSystem.getSynthesizer();
		synth.open();
		
		MidiChannel channel = synth.getChannels()[0];
		channel.programChange(12);
		channel.controlChange(7,127);
		
		for (int i=0; i < array.length; i++)
		{
			int note = array[i].freq.ordinal()+Pitch.ORDINAL_MIDI_OFFSET;
			
			channel.noteOn(note,90);
			sleep(AV_DELAY);
			
			// GUI ON
			this.i = i;
			on = true;
			repaint();
			
			sleep(ms);
			
			channel.noteOff(note);
			
			// GUI OFF
			on = false;
			repaint();
		}
		
		// sustain pause
		sleep(1000);
		
		channel.allNotesOff();
		synth.close();
	}
	*/
	
	public void play() throws MidiUnavailableException
	{
//		/* seed a constant rhythm?
//		 * 
//		 * 0 => 8 bars bubble
//		 * 3 => 8 bars selection
//		 * 7 => 8 bars insertion
//		 * 8 => 8 bars merge
//		 * 9 => 8 bars quick!
//		 */
//		Random gen = new Random(7);
//		
//		Synthesizer synth = MidiSystem.getSynthesizer();
//		synth.open();
//		
//		MidiChannel channel = synth.getChannels()[0];
//		channel.programChange(25);
//		channel.controlChange(7,127);
//		
//		int BASE = 150;//5;
//		int mode = 0;
//		int seq = 0;
//		for (int i=0; i < array.length; i++)
//		{
//			int note = array[i].freq.ordinal()+Pitch.ORDINAL_MIDI_OFFSET;
//			
//			channel.noteOn(note,90);
//			//sleep(AV_DELAY);
//			
//			// GUI ON
//			this.i = i;
//			on = true;
//			repaint();
//			
//			if (SWING)
//			{
//				switch (mode)
//				{
//				case 0: // 1 (2) (3)
//					sleep(3*BASE);
//					mode = gen.nextInt(3);
//					break;
//				case 1: // 1 (2) 3
//					if (seq == 0)
//					{
//						sleep(2*BASE);
//						seq++;
//					}
//					else
//					{
//						sleep(BASE);
//						seq = 0;
//						mode = gen.nextInt(3);
//					}
//					break;
//				case 2: // 1 2 3
//					sleep(BASE);
//					seq++;
//					if (seq == 3)
//					{
//						seq = 0;
//						mode = gen.nextInt(3);
//					}
//					break;
//				}
//				
//				// to end on a downbeat
//				if (seq == 0)
//				{
//					if (i == array.length - 5) mode = 2; else
//					if (i == array.length - 4) mode = 1; else
//					if (i == array.length - 3) mode = 0; else
//					if (i == array.length - 2) mode = 0;
//				}
//			}
//			else sleep(3*BASE);
//			
//			channel.noteOff(note);
//			
//			// GUI OFF
//			on = false;
//			repaint();
//		}
//		
//		// sustain pause
//		//try {Thread.sleep(3*BASE);}
//		try {Thread.sleep(1000);}
//		catch (InterruptedException ie) {ie.printStackTrace();}
//		
//		channel.allNotesOff();
//		synth.close();
	}
	
	private class Continuer implements KeyListener
	{
		
		@Override
		public void keyPressed(KeyEvent arg0)
		{
			if (pause != null && arg0.getKeyCode() == KeyEvent.VK_SPACE)
			{
				synchronized (pause)
				{
					pause.pause = false;
					pause.notify();
				}
			}
			else if (arg0.getKeyCode() == KeyEvent.VK_R)
				resume = true;
		}

		@Override
		public void keyReleased(KeyEvent arg0) {}

		@Override
		public void keyTyped(KeyEvent arg0) {}
	}
	
	private class Pause extends Thread
	{
		boolean pause = true;
		
		@Override
		public void run()
		{
			synchronized (this)
			{
				while (pause)
				{
					try {wait();}
					catch (InterruptedException e)
					{e.printStackTrace();}
				}
			}
		}
	}
	
	private void swap(int i, int j)
	{
		Pitch temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	
	public void bubbleSort() throws MidiUnavailableException
	{
		for (int k=array.length-1; k > 0; k--)
		{
			play();
			for (int i=0; i < k; i++)
			{
				if (array[i].compareTo(array[i+1]) > 0)
					swap(i, i+1);
			}
			
			// GUI updates
			sorted.add(k);
			
			repaint();
			pause();
			
		}
		play();
		sorted.add(0);
	}
	
	public void selectionSort() throws MidiUnavailableException
	{
		for (int i=0; i < array.length - 1; i++)
		{
			play();
			int min = i;

			for (int j=i+1; j < array.length; j++)
				if (array[j].compareTo(array[min]) < 0)
					min = j;

			swap(i, min);
			
			// GUI updates
			sorted.add(i);
			
			repaint();
			pause();
		}
		play();
		sorted.add(array.length-1);
	}
	
	public void insertionSort() throws MidiUnavailableException
	{
		sorted.add(0);
		repaint();
		pause();
		
		for (int j=1; j < array.length; j++)
		{
			play();
			int i = 0;

			while (array[j].compareTo(array[i]) > 0)
				i++;

			Pitch min = array[j];

			for (int k=0; k < j - i; k++)
				array[j - k] = array[j - k - 1];

			array[i] = min;
			
			// GUI updates
			sorted.add(j);
			repaint();
			pause();
		}
	}
	
	public void mergeSort() throws MidiUnavailableException
	{
		mergeSort(0, array.length);
	}
	
	private void mergeSort(int first, int last) throws MidiUnavailableException
	{
		if (last - first <= 1)
		{
			play();
			sorted.add(first);
			repaint();
			pause();
			return;
		}
		
		int mid = first + (last - first) / 2;

		mergeSort(first, mid);
		mergeSort(mid, last);
		
		play();
		
		merge(first, mid, last);
		
		for (int i=first; i < last; i++)
			sorted.add(i);
		repaint();
		pause();
	}

	private void merge(int first, int mid, int last)
	{
		Pitch[] aux = new Pitch[last - first];
		int i = first;
		int j = mid;

		for (int k = 0; k < aux.length; k++)
		{
			if (i == mid)
				aux[k] = array[j++];
			else if (j == last)
				aux[k] = array[i++];
			else if (array[j].compareTo(array[i]) < 0)
				aux[k] = array[j++];
			else
				aux[k] = array[i++];
		}

		System.arraycopy(aux, 0, array, first, aux.length);
	}
	
	public void quickSort() throws MidiUnavailableException
	{
		quicksort(0, array.length);
	}

	private void quicksort(int first, int last) throws MidiUnavailableException
	{
		if (last - first <= 1)
		{
			play();
			sorted.add(first);
			repaint();
			pause();
			return;
		}
		
		play();
		
		int pivot = partition(first, last);
		
		sorted.add(pivot);
		repaint();
		pause();

		if (pivot == first)
			quicksort(pivot + 1, last);
		else if (pivot == last - 1)
			quicksort(first, pivot);
		else
		{
			quicksort(first, pivot);
			quicksort(pivot + 1, last);
		}
	}

	private int partition(int first, int last)
	{
		int left = first + 1;
		int right = last - 1;

		while (left < right)
		{
			while (left < last - 1 && array[left].compareTo(array[first]) <= 0)
				left++;
			
			while (right > first && array[right].compareTo(array[first]) > 0)
				right--;

			if (left < right)
				swap(left, right);
		}

		if (array[first].compareTo(array[right]) > 0)
			swap(first, right);
		return right;
	}
	
	boolean isSorted()
	{
		boolean result = true;
		for (int i=0; i < array.length - 1; i++)
			if (array[i].compareTo(array[i+1]) > 0)
				result = false;
		return result;
	}
	
	public static void main(String[] args) throws MidiUnavailableException, SyntaxErrorException
	{
		JFrame frame = new JFrame("Funky Sort!");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		
		PitchSorter ps = new PitchSorter(new BluesScale(new Pitch("C1")),6);
		frame.getContentPane().add(ps);
		
		frame.pack();
		frame.setVisible(true);
		
		SWING = true;
		ps.pause();
		ps.quickSort();
		SWING = false;
		ps.play();
	}
}
